Some types of error correction codes, such as Low Density Parity Check (LDPC) codes, are commonly decoded using iterative decoding processes. The intra-order of operations that are performed during decoding iterations is referred to as scheduling. Various scheduling schemes and configurations for iterative decoding are known in the art.
For example, U.S. Pat. No. 8,504,890, whose disclosure is incorporated herein by reference, describes a decoder in which a code word is decoded by receiving a code word representation that includes a plurality of soft bits and iteratively updating the soft bits. Whether each soft bit participates in at least some of the iterations is determined according to a selection criterion, e.g., probabilistically, or according to the iteration number, or according to the soft bit's iteration history. For example, each soft bit might participate in some or all of the iterations with a probability that is a function of both the iteration number and a reliability measure of that soft bit. Preferably, the iterations are LDPC iterations in which variable nodes are addressed sequentially for exchanging messages with corresponding check nodes.
As another example, U.S. Patent Application Publication 2011/0314352, whose disclosure is incorporated herein by reference, describes methods and systems for reduced-complexity decoding of low-density parity-check (LDPC) information. An encoded input stream is received and decoded with one or more reduced-complexity min-sum or a-posteriori probability LDPC decoders. A v-node update rule in the reduced-complexity decoder is omitted.
In “A Generalization of Residual Belief Propagation for Flexible Reduced Complexity LDPC Decoding,” Proceedings of the IEEE Vehicular Technology Conference (VTC-Fall), San Francisco, Calif., Sep. 5-8, 2011, which is incorporated herein by reference, Beermann and Vary describe an Informed Dynamic Scheduling method providing different decoding strategies that dynamically decide which messages are passed throughout the decoding process. It was shown that the overall convergence can be sped up considerably and also more errors can be corrected with comparison to other (non-dynamic) decoding strategies. However, these strategies incur significant additional computational complexity in the procedure of selecting the messages to be updated in each decoding step. The authors propose two dynamic decoding strategies that allow for a flexible adaptation of the decoder's dynamics and reduce the additional complexity while maintaining, and in some cases exceeding, the convergence speed and error rate performance of known dynamic schedules.